/*
 * Transmissão de Dados - Trabalho 4
 *
 * Alex Oliveira   - 06/30403
 * Danilo Trindade - 06/82039
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "grafo.h"
#include "erros.h"

#define ALTURA 50
#define LARGURA 50
#define NOS 10
#define RAIO 8

static matriz_t test_matriz();
static grafo_t test_grafo();
static int qtdvizinhos(matriz_t m, int no);
static void is_connected(grafo_t grafo, int visitados[grafo.quant_vertices], int l);

/*
 * Verifica se alguma tabela foi atualizada. Retorna TRUE se for
 * e FALSE caso contrário.
 */
bool houve_atualizacao(grafo_t grafo, bool* atualizou){
	
	bool troca = false;
	
	for (int i = 0; i < grafo.quant_vertices; i++){
		if (atualizou[i]){
			troca = true;
		}
	}
	
	return(troca);
}


/*
 * Coloca todos os comutadores para trocar suas tabelas até estabilizar.
 */
void troca_tabelas(grafo_t grafo) {

	int **tabela_custo;
	bool *atualizou, *ira_atualizar;

	atualizou = calloc(grafo.quant_vertices, sizeof(bool));
	ira_atualizar = calloc(grafo.quant_vertices, sizeof(bool));
	tabela_custo = malloc(grafo.quant_vertices * sizeof(int *));

	/* Prepara tabela de custo antiga para simular paralelismo. */
	for (int i = 0; i < grafo.quant_vertices; i++){
		tabela_custo[i] = malloc(grafo.quant_vertices * sizeof(int));
		for (int j = 0; j < grafo.quant_vertices; j++){
			tabela_custo[i][j] = grafo.custo[i][j];
		}
		atualizou[i] = true;
		ira_atualizar[i] = false;
	}

	while(houve_atualizacao(grafo, atualizou)){ /* Se houve alguma atualizacao */

		for (int i = 0; i < grafo.quant_vertices; i++){ /* Percorre todos so nos */
			if (atualizou[i]) { /* Se o no atualizou */
				for (int j = 0; j < grafo.quant_vizinhos[i]; j++){ /* Percorre todos os vizinhos do no atualizado */
					for (int k = 0; k < grafo.quant_vertices; k++){ /* Pra todos os caminhos que existem no no atualizado */
						/* 
						 * Se o custo que este no atualizado tiver pro no 'k', ao ser somado ao custo q ele tem pra ir ate o
						 * no que eh o vizinho 'j' dele for menor q o custo desse vizinho ir ao no 'k', entao atualiza o
						 * custo e o caminho do vizinho em questao, e marca ele como ira ser atualizado pra enviar sua tabela
						 * na proxima iteracao.
						 *  
						 * usar o seguinte printf para verificar o if:
						 * printf("custo de %d pra %d: %d + custo de %d pra %d: %d < custo de %d pra %d: %d?\n",
						 * i, k, tabela_custo[i][k], i, grafo.vizinho[i][j], tabela_custo[i][grafo.vizinho[i][j]],
						 * grafo.vizinho[i][j], k, grafo.custo[grafo.vizinho[i][j]][k]);
						 * getchar();
						 */
						if ((tabela_custo[i][k] + tabela_custo[i][grafo.vizinho[i][j]]) < grafo.custo[grafo.vizinho[i][j]][k]){
							
							grafo.custo[grafo.vizinho[i][j]][k] = (tabela_custo[i][k] + tabela_custo[i][grafo.vizinho[i][j]]);
							grafo.caminho[grafo.vizinho[i][j]][k] = i;
							ira_atualizar[grafo.vizinho[i][j]] = true;
							
							for (int l = 0; l < grafo.quant_vertices; l++){
								if ((k != l) && (grafo.caminho[grafo.vizinho[i][j]][l] == k)){
									grafo.custo[grafo.vizinho[i][j]][l] = (grafo.custo[i][l] + grafo.custo[i][grafo.vizinho[i][j]]);
								}
							}
							
						}
					}
				}
			}
		}

		/* Monta o vetor de quais atualizaram pra proxima iteracao. */
		for (int i = 0; i < grafo.quant_vertices; i++){
			atualizou[i] = ira_atualizar[i];
			ira_atualizar[i] = false;
		}

		/* Atualiza tabela de custos com o valor antigo. */
		for (int i = 0; i < grafo.quant_vertices; i++){
			for (int j = 0; j < grafo.quant_vertices; j++){
				
				tabela_custo[i][j] = grafo.custo[i][j];
				
				
			}
		}

	}

	/* Atualiza caminhos otimizados. */
	for (int i = 0; i < grafo.quant_vertices; i++){
		for (int j = 0; j < grafo.quant_vertices; j++){
			if (grafo.caminho[i][j] != j){
				for (int k = 0; k < grafo.quant_vertices; k++){
					if (grafo.caminho[i][k] == j){
						grafo.caminho[i][k] = grafo.caminho[i][j];
					}
				}
			}
		}
	}
	
	/* Libera memoria utilizada. */
	for (int i = 0; i < grafo.quant_vertices; i++){
		free(tabela_custo[i]);
	}
	free(tabela_custo);
	free(atualizou);

	return;
}

/*
 * Lê do usuário um nó origem e um destino e escreve a menor rota e o custo dela.
 */
void mostra_rota(grafo_t grafo, int orig, int dest){
	
	int rota[grafo.quant_vertices], i = 0;
	
	rota[i] = orig;
	
	/* Monta a rota que será seguida pra ir de orig a dest. */
	while (rota[i] != dest){
		i++;
		rota[i] = grafo.caminho[rota[i-1]][dest];
	}
	
	/* Imprime o melhor caminho, seu custo e o número de pulos que faz. */
	printf("Menor caminho do no %d para o no %d:\n Pulos: %d\n Rota: %d -> ", orig, dest, i, orig);
	for (int j = 1; j<i; j++){
		printf("%d -> ", rota[j]);
	}
	printf("%d\n Custo: %d\n", dest, grafo.custo[orig][dest]);
	
	return;
}

int main() {

	matriz_t m = test_matriz();
	grafo_t grafo;
	grafo = test_grafo(m, RAIO);

	/* imprime o grafo */
	for (int i = 0; i < grafo.quant_vertices; ++i) {
		printf("no %d\n", i);
		for (int j = 0; j < grafo.quant_vizinhos[i]; ++j) {
			printf("\tviz[%d]: %d, custo: %d\n", j, grafo.vizinho[i][j], grafo.custo[i][j]);
		}
	}

	printf("vizinhos de 0:\n");
	for (int i = 0; i < grafo.quant_vizinhos[0]; i++){
		printf("%d, ", grafo.vizinho[0][i]);
	}

	printf("Tabela pro no 0 antes da troca:\n");
	for (int i = 0; i < grafo.quant_vertices; i++){
		printf("caminho pra %d: %d; custo: %d\n", i, grafo.caminho[0][i], grafo.custo[0][i]);
	}
	troca_tabelas(grafo);
	printf("Tabela pro no 0 depois da troca:\n");
	for (int i = 0; i < grafo.quant_vertices; i++){
		printf("caminho pra %d: %d; custo: %d\n", i, grafo.caminho[0][i], grafo.custo[0][i]);
	}

	for (int i = 0; i < grafo.quant_vertices; i++){
		for (int j = 0; j < grafo.quant_vertices; j++){
			if (i != j){
				mostra_rota(grafo,i,j);
			}
		}
	}

	/* Teste de apagar a matriz. */
	del_matriz(m);

	/* Teste de apagar o grafo. */
	del_grafo(grafo);

	return 0;
}


/*
 * Testa se a new_matriz coloca os vizinhos dentro do raio.
 */
matriz_t test_matriz() {

	/* Testa criação da matriz. */
	matriz_t m = new_matriz(ALTURA, LARGURA, NOS, RAIO);

	/* Testa quantidade de vizinhos. */
	for (int i = 0; i < NOS; i++) {
		if (qtdvizinhos(m, i) < 1) {
			erro = ERRUNDEF;
			puts("ERRO: Quantidade de vizinhos está errada.");
		}
	}



	if (!erro) {
		puts("Teste matriz: OK");
	} else {
		puts("Teste matriz: FALHOU");
	}
	return m;
}


/*
 * Conta a quantidade de vizinhos que um nó tem.
 */
int qtdvizinhos(matriz_t m, int no) {
	int count = 0;

	/* Percorre o quadrado de distância até RAIO contando os vizinhos. */
	for (int y = m.no[no].y - RAIO; y <= m.no[no].y + RAIO; y++) {
		for (int x = m.no[no].x - RAIO; x <= m.no[no].x + RAIO; x++) {
			if (m.celula[y][x] >= 0) {
				count++;
			}
		}
	}

	return count;
}

/*
 * Testa se a new_matriz coloca os vizinhos dentro do raio.
 */
grafo_t test_grafo(matriz_t m, int raio) {

	int funfando = 1;

	/* Testa criação do grafo. */
	grafo_t grafo = new_grafo(m, raio);

	/* Testa consistencia de vizinhos. */
	for (int i = 0; ((i < grafo.quant_vertices)&&(funfando)); i++){
		for (int j = 0; ((j < grafo.quant_vizinhos[i])&&(funfando)); j++){
			funfando = 0;
			for (int k = 0; ((k < grafo.quant_vizinhos[grafo.vizinho[i][j]]) && !(funfando)); k++){
				if (grafo.vizinho[grafo.vizinho[i][j]][k] == i){
					funfando = 1;
				}
			}
			if (funfando == 0) {
				goto ops;
			}
		}
	}

	ops:

	/* Testa conectividade do grafo. */
	if ((funfando) && (grafo.quant_vertices > 1)) {

		int visitados[grafo.quant_vertices];
		for (int i = 0; i < grafo.quant_vertices; i++){
			visitados[i] = 0;
		}

		is_connected(grafo, visitados, 0);

		for (int i = 0; i < grafo.quant_vertices; i++){
			if (!(visitados[i])){
				funfando = 0;
			}
		}
	}

	/* Imprime resultado do teste. */
	if (funfando){
		puts("Teste grafo: OK");
	} else {
		puts("Teste grafo: FALHOU");
	}

	return(grafo);

}

/* Função que verifica se o grafo é conectado. */
static void is_connected(grafo_t grafo, int visitados[grafo.quant_vertices], int l){

	visitados[l] = 1;
	for (int j = 0; j < grafo.quant_vizinhos[l]; j++){
		if (!(visitados[grafo.vizinho[l][j]])){
			is_connected(grafo, visitados, grafo.vizinho[l][j]);
		}
	}

	return;

}
